package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class 打印一个字符串的子序列 {
    public static void main(String[] args) {
//        //从第0个元素开始
//        List<String> ans = new ArrayList<>();
//        Set<String> ans1 = new HashSet<>();
//        print("adaf", 0, "", ans);
//        printNoRepeat("adaf", 0, "", ans1);
//        ans.stream().forEach(s->{
//            System.out.println(s);
//        });
    }

    private static void print(String str, int index, String path, List<String> ans) {
        if (index == str.length()) {
            ans.add(path);
            return;
        }
        print(str, index + 1, path, ans);//不要当前元素
        print(str, index + 1, path + String.valueOf(str.charAt(index)), ans);//要当前元素

    }

    /**
     * 去重版本
     * @param str
     * @param index
     * @param path
     * @param ans
     */
    private static void printNoRepeat(String str, int index, String path, Set<String> ans) {
        if (index == str.length()) {
            ans.add(path);
            return;
        }
        printNoRepeat(str, index + 1, path, ans);//不要当前元素
        printNoRepeat(str, index + 1, path + String.valueOf(str.charAt(index)), ans);//要当前元素

    }
}
